package antonst.list;

import java.util.Comparator;
import java.util.RandomAccess;

public class MyCollections {

	public static <T extends Comparable<T>> void sort(MyList<T> list) {
		try {
			RandomAccess ra = (RandomAccess) list;
			quickSort(list, new NaturalCompare<T>());
		} catch (ClassCastException e) {
			bubbleSort(list, new NaturalCompare<T>());
		}
	}

	public static <T> void sort(MyList<T> list, Comparator c) {
		try {
			RandomAccess ra = (RandomAccess) list;
			quickSort(list, new CompareWithComparator<T>(c));
		} catch (ClassCastException e) {
			bubbleSort(list, new CompareWithComparator<T>(c));
		}

	}

	public static <T> void swap(MyList<T> list, int i, int j) {
		T iElement = list.get(i);
		list.set(i, list.get(j));
		list.set(j, iElement);
	}

	public static <T> void copy(MyList<? super T> dest, MyList<? extends T> src) {
		for (T element : src) {
			dest.add(element);
		}
	}

	public static <T> void reverse(MyList<T> list) {
		int size = list.size();
		if (size > 1) {
			int upTo = size/2;
			for (int leftElementIndex=0; leftElementIndex < upTo; leftElementIndex++) {
				T temp = list.get(leftElementIndex);
				int rightElementIndex = size - 1 - leftElementIndex;
				list.set(leftElementIndex, list.get(rightElementIndex));
				list.set(rightElementIndex, temp);
			}
		}
	}

	public static <T extends Comparable<T>> int binarySearch(RandomAccess list, T key) {
		MyList<T> myList = (MyList<T>) list;
		if (myList.size() > 0) {
			return partitialBinarySearch(myList, key, 0, myList.size()-1);
		} else {
			return -1;
		}	

	}

	private static <T extends Comparable<T>> int partitialBinarySearch(MyList<T> list, T key, int searchFrom, int searchUpTo) {
			int middlePosition = (searchUpTo - searchFrom + 1)/2 + searchFrom;
			int searchResult = key.compareTo(list.get(middlePosition));
			if (searchResult == 0) {
				return middlePosition;
			} else if (searchResult < 0) {
				if (searchFrom == middlePosition) {
					return -searchFrom - 1;
				} else {
					return partitialBinarySearch(list, key, searchFrom, middlePosition-1);
				}
			} else {
				if (searchUpTo == middlePosition) {
					return -(searchUpTo+1) - 1;
				} else {
					return partitialBinarySearch(list, key, middlePosition+1, searchUpTo);
				}
			}
	}

	private static <T> void quickSort(MyList<T> list, UniversalCompare<T> comparator) {
		if (list.size() > 1) {
			partitialQuickSort(list, 0, list.size()-1, comparator);
		}
	}

	private static <T> void partitialQuickSort(MyList<T> list,
			int startIndex, int endIndex, UniversalCompare<T> comparator) {
		int sortSize = endIndex - startIndex + 1;
		if (sortSize == 2) {
			if (comparator.compare(list.get(startIndex), 
					(list.get(endIndex))) > 0) {	
				T temp = list.get(startIndex);
				list.set(startIndex, list.get(endIndex));
				list.set(endIndex, temp);
			}
		} else if (sortSize > 2) {
			int propPosition = sortSize / 2 + startIndex;
			int leftPosition = startIndex;
			int rightPosition = endIndex;
			while (leftPosition < rightPosition) {
				while (comparator.compare(list.get(leftPosition),
						list.get(propPosition)) < 0
						&& leftPosition < propPosition)
					leftPosition++;
				while (comparator.compare(list.get(rightPosition), 
						list.get(propPosition)) > 0
						&& rightPosition > propPosition)
					rightPosition--;
				if (leftPosition != rightPosition) {
					swap(list, leftPosition, rightPosition);
					if (propPosition == leftPosition){
						propPosition = rightPosition;
						leftPosition++;
					} else if (propPosition == rightPosition) {
						propPosition = leftPosition;
						rightPosition--;
					} else {
						leftPosition++;
						rightPosition--;
					}
				}
			}
			partitialQuickSort(list, startIndex, propPosition-1, comparator);
			partitialQuickSort(list, propPosition+1, endIndex, comparator);
		}
	}

	private static <T> void bubbleSort(MyList<T> list, UniversalCompare<T> comparator) {
		int size = list.size();
		for (int outerBound = size; outerBound > 0; outerBound--) {
			for (int i = 0; i < outerBound - 1; i++) {
				if (comparator.compare(list.get(i), list.get(i + 1)) > 0) {
					swap(list, i, i + 1);
				}
			}
		}
	}

	private static interface UniversalCompare<T> {
		int compare(T o1, T o2);
				
	}

	private static class NaturalCompare<T extends Comparable<T>> implements UniversalCompare<T> {

		@Override
		public int compare(T o1, T o2) {
			return o1.compareTo(o2);
		}
		
	}

	private static class CompareWithComparator<T> implements UniversalCompare<T> {
		
		private final Comparator<T> comparator;
		
		public CompareWithComparator(Comparator<T> comparator) {
			this.comparator = comparator;	
		}

		@Override
		public int compare(T o1, T o2) {
			return comparator.compare(o1, o2);
		}

	}

}
